class Solution(object):
    def specialGrid(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        if n == 0:
            return [[0]]
        
        size = 2 ** n
        grid = [[0 for _ in range(size)] for _ in range(size)]
        
        # 递归填充四个象限
        def fill_quadrants(x, y, s, start_val):
            if s == 1:
                grid[x][y] = start_val
                return
            
            new_size = s // 2
            
            # 计算四个象限的起始值
            start_tr = start_val
            start_br = start_tr + new_size * new_size
            start_bl = start_br + new_size * new_size
            start_tl = start_bl + new_size * new_size
            
            # 填充右上角象限
            fill_quadrants(x, y + new_size, new_size, start_tr)
            # 填充右下角象限
            fill_quadrants(x + new_size, y + new_size, new_size, start_br)
            # 填充左下角象限
            fill_quadrants(x + new_size, y, new_size, start_bl)
            # 填充左上角象限
            fill_quadrants(x, y, new_size, start_tl)
        
        fill_quadrants(0, 0, size, 0)
        return grid